ElectroCardioGram （ECG） data usually contain many diseases， and ECG diagnosis is a typical multi-label classification problem. In RAndom k-labELsets （RAKEL） algorithm， one of multi-label classification methods， all labels are randomly decomposed into several labelsets of size k， and a Label Powerset （LP） classifier is established for training； however， the lack of sufficient consideration of correlation between labels makes the LP classifier obtain quite few samples corresponding to certain label combinations， which affects the prediction performance. To fully consider the correlation between labels， a Bayesian Network-based RAKEL （BN-RAKEL） algorithm was proposed. Firstly， the correlation between labels was found by Bayesian network to determine the candidate labelsets. Then， a feature selection method based on information gain was applied to construct the optimal feature space for each label， and the optimal feature space similarity was used for each candidate label subset to detect its correlation degree， determing the final labelsets with strong correlation. Finally， the LP classifiers were trained in the optimal feature space of the corresponding labelsets. A comparison with K-Nearest Neighbors for Multi-label Learning （ML-KNN）， RAKEL， Classifier Chains （CC） and FP-Growth based RAKEL algorithm named FI-RAKEL on the real ECG dataset showed that the proposed algorithm achieved a minimum improvement of 3.6 percentage points and 2.3percentage points in recall and F-score， respectively. Experimental results show that BN-RAKEL algorithm has good prediction performance， and can effectively improve the ECG diagnosis accuracy.